package com.leetcode.根据数据结构分类.数组;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: xiaomi
 * @date: 2021/2/13
 * @description: 448. 找到所有数组中消失的数字
 * https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array/
 */
public class A_448_找到所有数组中消失的数字 {

    public static void main(String[] args) {

    }

    /**
     * 题目要求不适用额外空间--> 没有思路
     * 1.由于只出现 1-n ，所以创建一个数组；
     * 2.
     *
     * @param nums
     * @return
     */
    public List<Integer> findDisappearedNumbers(int[] nums) {
        int len = nums.length;
        int[] arr = new int[len + 1];
        for (int i = 0; i < len; i++) {
            arr[nums[i]]++;
        }
        List<Integer> res = new ArrayList<>();
        //标记完毕
        for (int i = 1; i <= len; i++) {
            if (arr[i] == 0) {
                res.add(i);
            }
        }
        return res;
    }


}
